import java.util.Scanner;

public class code1 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //1.输入
        int t = scan.nextInt();


        for(int i=0;i<t;i++) {
            long n = scan.nextLong();
            long m = scan.nextLong();
            long p = scan.nextLong();
            long res = qmi(n,m,p);
            System.out.println(res);
        }

    }

    public static long qmi(long a,long b,long p) {//对p取模
        long res = 1;
        while(b>0) {
            if((b%2)==1) {//记得加括号
                res = res *a % p;//b为奇数，乘一个a到res里
            }
            a = a*a%p;//底数平方，指数除以2
            b>>=1;
        }
        return res;
    }
}
